//
// Created by wenyaxi on 24-10-30.
//

#include <common.h>

class Solution {
public:
    vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
        std::deque<TreeNode *> dq;
        vector<vector<int> > res;
        if (root == nullptr) {
            return res;
        }
        dq.push_back(root);
        int c = 1;
        bool flag = true;
        while (!dq.empty()) {
            int cnt = 0;
            int n = c;
            if (flag) {
                vector<int> v_tmp;
                for (int i = 0; i < n; i++) {
                    TreeNode *cur = dq.front();
                    dq.pop_front();

                    v_tmp.push_back(cur->val);
                    if (cur->left != nullptr) {
                        dq.push_back(cur->left);
                        cnt++;
                    }
                    if (cur->right != nullptr) {
                        dq.push_back(cur->right);
                        cnt++;
                    }
                }
                res.push_back(std::move(v_tmp));
                flag = false;
            } else {
                vector<int> v_tmp;
                for (int i = 0; i < n; i++) {
                    TreeNode *cur = dq.back();
                    dq.pop_back();

                    v_tmp.push_back(cur->val);

                    if (cur->right != nullptr) {
                        dq.push_front(cur->right);
                        cnt++;
                    }
                    if (cur->left != nullptr) {
                        dq.push_front(cur->left);
                        cnt++;
                    }
                }
                res.push_back(std::move(v_tmp));
                flag = true;
            }
            c = cnt;
        }
        return res;
    }
};

void test() {
    Solution s;
    auto *n0 = new TreeNode(0);
    auto *n1 = new TreeNode(1);
    auto *n2 = new TreeNode(2);
    auto *n3 = new TreeNode(3);
    auto *n4 = new TreeNode(4);
    auto *n5 = new TreeNode(5);
    auto *n6 = new TreeNode(6);

    n0->left = n1;
    n0->right = n2;
    n1->left = n3;
    n1->right = n4;
    n2->left = n5;
    n2->right = n6;

    auto lines = s.zigzagLevelOrder(n0);
    for (const auto &v: lines) {
        cout << printer::arrayToString(v) << endl;
    }
}

void test1() {
    std::deque<TreeNode *> dq;
    cout << dq.empty() << endl;
}

int main(int argc, char *argv[]) {
    test();
    return 0;
}
